require 'rubygems'
require 'ruby-debug'

DirectElimination = rule {
  id :direct_elimination
  desc "Eliminates all candidates from a field that occur as solutions in the fields it sees."
  reason ":candidate is present in :elim_field"
  
  logic {
    solved_fields.each do |field|
      (field.seen_fields - [field]).each { |seen_field| eliminate(seen_field, field.value, :elim_field => field) }
    end
  }
}


HiddenSingle = rule {
  id :hidden_single
  desc "If a field is the only one to contain a candidate within a house, all other candidates are removed."
  reason ":candidate is alone in :house"
  
  logic {
    houses.each do |house|
      solved_fields = house.select { |f| f.solved? }
      unsolved_fields = house - solved_fields
      
      unsolved_fields.each do |field|
        field.possibilities.each do |candidate|
          if unsolved_fields.select { |g| g.possibilities.include?(candidate) }.size == 1 && solved_fields.all? { |g| !g.possibilities.include?(candidate) }
            set(field, candidate, :house => house)
          end
        end
      end
    end
  }
}


NakedPair = rule {
  id :naked_pair
  reason ":candidate is part of a naked pair"
  
  logic {
    houses.each do |house|
      house.comb(2).each do |pair|
        f, g = pair
        if (f.possibilities.size == 2) && (f.possibilities == g.possibilities)
          (house - pair).each { |h| eliminate(h, f.possibilities) }
        end
      end
    end
  }
}


HiddenPair = rule {
  id :hidden_pair
  
  logic {
    houses.each do |house|
      [*1..9].comb(2).each do |pair|
        i, j = pair
        # find all fields which can contain both i and j
        possible_fields = house.select { |f| pair.all? { |k| f.possibilities.include?(k) } }
        
        if possible_fields.size == 2 && possible_fields.any? { |f| f.possibilities.size > 2 } # verify that it's a pair and that there's something left to eliminate
          # verify that there are no other fields that can contain either i or j
          pair_found = house.all? do |f|
            unless possible_fields.include?(f)
              !f.possibilities.include?(i) && !f.possibilities.include?(j)
            else
              true
            end
          end
          
          possible_fields.each { |f| set(f, pair) } if pair_found
        end
      end
    end
  }
}


OldHiddenSingle = rule {
  id :old_hidden_single
  name "hidden single (old)"
  
  logic {
    houses.each do |house|
      (1..9).each do |i|
        possible_fields = house.select { |f| f.possibilities.include?(i) }      
        set(possible_fields.first, i) if possible_fields.size == 1 && possible_fields.first.possibilities.size >= 1
      end
    end
  }
}


LockedCandidatesPointing = rule {
  id :locked_candidates_pointing
  name "locked candidates: pointing"
  
  logic {
    squares.each do |square|
      (1..9).each do |i|
        possible_fields = square.select { |f| f.possibilities.include?(i) }

        if !possible_fields.empty?
          check_column = possible_fields.first.x
          if possible_fields.all? { |f| f.x == check_column } # same x-coordinate => same column
            # remove this digit from all the fields in the column that aren't part of this square
            columns[check_column].each { |f| eliminate(f, i) unless square.include?(f) }
          end
          
          check_row = possible_fields.first.y
          if possible_fields.all? { |f| f.y == check_row } # same y-coordinate => same row
            # remove this digit from all the fields in the row that aren't part of this square
            rows[check_row].each { |f| eliminate(f, i) unless square.include?(f) }
          end
        end
      end
    end  
  }
}


LockedCandidatesClaiming = rule {
  id :locked_candidates_claiming
  name "locked candidates: claiming"
  
  logic {
    lines.each do |line|
      (1..9).each do |i|
        possible_fields = line.select { |f| f.possibilities.include?(i) }

        if !possible_fields.empty?
          check_square = possible_fields.first.containing_square_pos
        
          if possible_fields.all? { |f| f.containing_square_pos == check_square } # all fields are in the same square
            squares[check_square].each { |f| eliminate(f, i) unless line.include?(f) } 
          end
        end
      end
    end  
  }
}


NakedTriple = rule {
  id :naked_triple
  
  logic {
    houses.each do |house|
      house.comb(3).each do |triple|
        f, g, h = triple
        all_possibilities = (f.possibilities + g.possibilities + h.possibilities).uniq
        if (all_possibilities.size == 3) && triple.all? { |field| field.possibilities.size >= 2 }
          (house - triple).each { |h| eliminate(h, all_possibilities) }
        end
      end
    end
  }
}


NakedQuad = rule {
  id :naked_quad
  
  logic {
    houses.each do |house|
      house.comb(4).each do |quad|
        f, g, h, i = quad
        all_possibilities = (f.possibilities + g.possibilities + h.possibilities + i.possibilities).uniq
        if (all_possibilities.size == 4) && quad.all? { |field| field.possibilities.size >= 2 }
          (house - quad).each { |h| eliminate(h, all_possibilities) }
        end
      end
    end
  }
}


NakedSubset = rule { # this rule is a generalisation of NakedPair, NakedTriple and NakedQuad. Slow and not very useful!
  id :naked_subset
  
  logic {
    houses.each do |house|
      house.power_set(2..4).each do |candidates|
        all_possibilities = candidates.collect { |c| c.possibilities }.flatten.uniq
        if (all_possibilities.size == candidates.size) && candidates.all? { |field| field.possibilities.size >= 2 }
          (house - candidates).each { |h| eliminate(h, all_possibilities) }
        end
      end
    end
  }
}


AlmostLockedPairLine = rule {
  id :almost_locked_pair_line
  name "almost locked pair: line"
  
  logic {
    chutes.each do |chute|
      chute.each do |line|
        squares = (0..2).collect { |i| line[3*i].containing_square }

        squares.each do |square|
          intersection = line & square
          
          [*1..9].comb(2).each do |pair|
            i, j = pair
            line_fields = (line - intersection).select { |f| f.possibilities == pair } # only fields that can only contain i and j, and are outside the intersection
            
            if line_fields.size == 1 && ((line - intersection) - line_fields).all? { |f| !f.possibilities.include?(i) && !f.possibilities.include?(j) }
              square_fields = (square - intersection).select { |f| f.possibilities == pair }
              ((square - intersection) - square_fields).each { |f| eliminate(f, pair) } if square_fields.size == 1
            end
          end
        end
      end
    end  
  }
}


AlmostLockedPairSquare = rule {
  id :almost_locked_pair_square
  name "almost_locked_pair: square"
  
  logic {
    chutes.each do |chute|
      chute.each do |line|
        squares = (0..2).collect { |i| line[3*i].containing_square }

        squares.each do |square|
          intersection = line & square
          
          [*1..9].comb(2).each do |pair|
            i, j = pair
            square_fields = (square - intersection).select { |f| f.possibilities == pair } # only fields that can only contain i and j, and are outside the intersection
            
            if square_fields.size == 1 && ((square - intersection) - square_fields).all? { |f| !f.possibilities.include?(i) && !f.possibilities.include?(j) }
              line_fields = (line - intersection).select { |f| f.possibilities == pair }
              ((line - intersection) - line_fields).each { |f| eliminate(f, pair) } if line_fields.size == 1
            end
          end
        end
      end
    end
  }
}


Scanning = rule {
  id :scanning
  
  logic {
    chutes.each do |chute|
      minilines = chute.inject([]) { |m, line| m += [line[0..2], line[3..5], line[6..8]] } # split 3 lines into 9 minilines
      (1..9).each do |i|
        patterns = [[0,4,8], [0,7,5], [3,1,8], [3,7,2], [6,1,5], [6,4,2]] # the 6 possible scanning patterns
        minilines.each_with_index do |miniline, m_index|
          if miniline.all? { |f| !f.possibilities.include?(i) } # this miniline can't contain the digit
            # remove all patterns that contain this miniline (because they can not occur)
            patterns.reject! { |p| p.include?(m_index) }
          end
                  
          square = m_index % 3
          other_miniline_indices = [square, square + 3, square + 6] - [m_index]
        end

        disallowed_minilines = minilines - patterns.flatten.uniq.collect { |j| minilines[j] }
        disallowed_minilines.each { |m| m.each { |f| eliminate(f, i) } } # remove this possibility from all excluded minilines
      end
    end
  }
}


AffirmativeScanning = rule {
  id :affirmative_scanning
  
  logic {
    chutes.each do |chute|
      minilines = chute.inject([]) { |m, line| m += [line[0..2], line[3..5], line[6..8]] } # split 3 lines into 9 minilines
      (1..9).each do |i|
        patterns = [[0,4,8], [0,7,5], [3,1,8], [3,7,2], [6,1,5], [6,4,2]] # the 6 possible scanning patterns
        minilines.each_with_index do |miniline, m_index|
          if miniline.all? { |f| !f.possibilities.include?(i) } # this miniline can't contain the digit
            # remove all patterns that contain this miniline (because they can not occur)
            patterns.reject! { |p| p.include?(m_index) }
          end
                  
          square = m_index % 3
          other_miniline_indices = [square, square + 3, square + 6] - [m_index]
          
          miniline_must_contain_digit = miniline.any? { |f| f.value == i }
          miniline_must_contain_digit ||= (minilines[other_miniline_indices[0]].all? { |f| !f.possibilities.include?(i) } &&
                                           minilines[other_miniline_indices[1]].all? { |f| !f.possibilities.include?(i) })
          
          if  miniline_must_contain_digit # this miniline MUST contain the digit.. this check is NOT complete
            # remove all patterns that contain the other minilines of the same box
            patterns.reject! { |p| p.include?(other_miniline_indices[0]) || p.include?(other_miniline_indices[1]) }
          end
        end

        disallowed_minilines = minilines - patterns.flatten.uniq.collect { |j| minilines[j] }
        disallowed_minilines.each { |m| m.each { |f| eliminate(f, i) } } # remove this possibility from all excluded minilines
      end
    end
  }  
}


HiddenSubset = rule {
  id :hidden_subset
  
  logic {
    houses.each do |house|
      solved_values = house.select { |f| f.solved? }.collect { |f| f.value }
      values_to_investigate = [*1..9] - solved_values # removing the solved values yields a better performance

      values_to_investigate.power_set(2..4).each do |inv_set|
        possible_fields = house.select { |f| inv_set.any? { |i| f.possibilities.include?(i) } }
        
        if possible_fields.size == inv_set.size && possible_fields.any? { |f| f.possibilities.size > inv_set.size }
          # verify set size and that there's something left to eliminate
          possible_fields.each { |f| set(f, inv_set) }
        end
      end
    end
  }
}

RowXWing = rule {
  id :row_xwing
  name "row X-wing"
  
  logic {
    rows.comb(2).each do |pair|
      r, s = pair
      (1..9).each do |i| # TODO: remove solved values? not so easy!
        l_fields = r.select { |f| f.possibilities.include?(i) }
        r_fields = s.select { |f| f.possibilities.include?(i) }
        if l_fields.size == 2 && l_fields.collect { |f| f.x } == r_fields.collect { |f| f.x } # column indices should be identical
        l_fields.collect { |f| f.x }.each do |k| # iterate over columns
            (columns[k] - l_fields - r_fields).each { |f| eliminate(f, i) }
          end
        end
      end
    end
  }
}


ColumnXWing = rule {
  id :column_xwing
  name "column X-wing"

  logic {
    columns.comb(2).each do |pair|
      c, d = pair
      (1..9).each do |i| # TODO: remove solved values? niet zo simpel!
        l_fields = c.select { |f| f.possibilities.include?(i) }
        r_fields = d.select { |f| f.possibilities.include?(i) }
        if l_fields.size == 2 && l_fields.collect { |f| f.y } == r_fields.collect { |f| f.y } # row indices should be identical
          l_fields.collect { |f| f.y }.each do |k|
            (rows[k] - l_fields - r_fields).each { |f| eliminate(f, i) }
          end
        end
      end
    end
  }
}


# TODO: combine RowXWing and ColumnXWing? combine method?


# row-column XY-wing can eliminate at most one candidate in one cell, whereas this one can affect up to five cells, so it's not worth it to implement it
SquareLineXYWing = rule {
  id :square_line_xywing
  name "square-line XY-wing"
  
  logic {
    lines.each do |line|
      line.select { |f| f.possibilities.size == 2 }.each do |pivot| # every cell in the line with exactly 2 candidates can function as a pivot cell.
        square = pivot.containing_square
        intersection = line & square
        
        # either XZ is in the square and YZ is in the line, or vice versa! CONSIDER BOTH OPTIONS!
        pivot.possibilities.each do |w|
          # let's try and find a possible XZ pincer cell in the square
          possible_square_pincers = (square - intersection).select { |f| f.possibilities.size == 2 && f.possibilities.include?(w) }
          possible_square_pincers.each do |square_pincer|
            z = (square_pincer.possibilities - [w]).first
            # find a corresponding YZ pincer cell in the line
            possible_line_pincers = (line - intersection).select { |f| f.possibilities == ((pivot.possibilities - [w]) + [z]).sort } # sort is important, y might > z!
            possible_line_pincers.each do |line_pincer|
              other_intersection = (square_pincer.containing_column + square_pincer.containing_row) & line_pincer.containing_square
              # line of square pincer and square of line pincer
              # PROBLEM: we can't know if the line is row or a column. However, if we combine both,
              # the interesection will never contain fields of the type of line we aren't considering.
              # I probably won't have a clue what this means anymore if I read this tomorrow.
              (intersection + other_intersection).each { |f| eliminate(f, z) } # up to five possible removals!
            end
          end
        end
      end
    end
  }
}


WeirdHiddenSingle = rule {  # a different approach which seems to be slower.
  id :weird_hidden_single
  name "hidden single (weird)"
  
  logic {
    # It's not equivalent with HiddenSingle because it does things in a different order
    unsolved_fields.each do |f|
      f.possibilities.each do |c|
        # if c is alone in one of the containing houses, we can eliminate all other candidates!
        f.containing_houses.each do |h|
          set(f, c) if h.select { |g| g.possibilities.include?(c) }.size == 1
        end
      end
    end
  }
}


=begin
When there are
 * only 2 candidates for a value, in each of 2 different houses of the same kind,
 * and these candidates lie also on 2 other houses of the same kind,

then all other candidates for that value can be eliminated from the latter two houses.
=end

GeneralisedXWing = rule {
  id :generalised_xwing
  name "generalised X-wing"
  
  logic {
    house_types = [rows, columns, squares]
    
    house_types.var(2).each do |types_pair|
      a, b = types_pair # a is the type of house where we look for aligned candidates,
                        # b is the type of house where we will eliminate the candidates.
                         
      a.comb(2).each do |houses_pair| # later veralgemenen naar subset!
        intersection = b.select { |h_b| houses_pair.all? { |h_a| [h_a, h_b].intersect? } } # only consider the type b houses that intersect with the chosen type a ones
  
        values_to_test = [*1..9] - houses_pair.union.select(&:solved?).collect(&:value)
        values_to_test.each do |i|
          fields_set = houses_pair.collect { |house| house.select { |f| f.possibilities.include?(i) } }
          intersecting_houses_set = fields_set.collect { |s| s.collect { |f| intersection.select { |house| house.include?(f) }.first } }
          next if intersecting_houses_set.union.include?(nil)
          # for each field in each fields combination in the set:
          # find the house in 'intersection' which it is part of (intersection.select { |house| house.include?(f) }.first)
          
          if fields_set.all? { |s| s.size == 2 } && intersecting_houses_set.all_equal?
            intersecting_houses_set.first.each do |house|
              (house - fields_set.union).each { |f| eliminate(f, i) }
            end
          end
        end
      end
    end
  }
}


GeneralisedFish = rule { # encompasses regular X-Wing (row & column), Locked candidates (pointing & claiming), swordfish and jellyfish. VERY general!
  id :generalised_fish
  
  logic {
    house_types = [rows, columns, squares]
    
    house_types.var(2).each do |types_pair|
      a, b = types_pair # a is the type of house where we look for aligned candidates,
                        # b is the type of house where we will eliminate the candidates.
                         
      a.power_set(2..4).each do |houses_set|
        intersection = b.select { |h_b| houses_set.all? { |h_a| [h_a, h_b].intersect? } } # only consider the type b houses that intersect with the chosen type a ones
  
        values_to_test = [*1..9] - houses_set.union.select(&:solved?).collect(&:value)
        values_to_test.each do |i|
          fields_set = houses_set.collect { |house| house.select { |f| f.possibilities.include?(i) } }
          intersecting_houses_set = fields_set.collect { |s| s.collect { |f| intersection.select { |house| house.include?(f) }.first } }
          all_intersecting_houses = intersecting_houses_set.union
          next if all_intersecting_houses.include?(nil)
          # for each field in each fields combination in the set:
          # find the house in 'intersection' which it is part of (intersection.select { |house| house.include?(f) }.first)
          
          if all_intersecting_houses.size == houses_set.size && fields_set.all? { |s| s.size >= 2 }
            all_intersecting_houses.each do |house|
              (house - fields_set.union).each { |f| eliminate(f, i) }
            end
          end
        end
      end
    end
  }
}


GeneralisedSwordfish = rule {
  id :generalised_swordfish
  
  logic {
    house_types = [rows, columns, squares]
    
    house_types.var(2).each do |types_pair|
      a, b = types_pair # a is the type of house where we look for aligned candidates,
                        # b is the type of house where we will eliminate the candidates.
                         
      a.comb(3).each do |houses_set|
        intersection = b.select { |h_b| houses_set.all? { |h_a| [h_a, h_b].intersect? } } # only consider the type b houses that intersect with the chosen type a ones
  
        values_to_test = [*1..9] - houses_set.union.select(&:solved?).collect(&:value)
        values_to_test.each do |i|
          fields_set = houses_set.collect { |house| house.select { |f| f.possibilities.include?(i) } }
          intersecting_houses_set = fields_set.collect { |s| s.collect { |f| intersection.select { |house| house.include?(f) }.first } }
          all_intersecting_houses = intersecting_houses_set.union
          next if all_intersecting_houses.include?(nil)
          # for each field in each fields combination in the set:
          # find the house in 'intersection' which it is part of (intersection.select { |house| house.include?(f) }.first)
          
          if all_intersecting_houses.size == houses_set.size && fields_set.all? { |s| s.size >= 2 }
            all_intersecting_houses.each do |house|
              (house - fields_set.union).each { |f| eliminate(f, i) }
            end
          end
        end
      end
    end
  }
}


Swordfish = rule {
  id :swordfish
  
  logic {
    house_types = [rows, columns]
    
    house_types.var(2).each do |types_pair|
      a, b = types_pair # a is the type of house where we look for aligned candidates,
                        # b is the type of house where we will eliminate the candidates.
                         
      a.comb(3).each do |houses_set|
        intersection = b.select { |h_b| houses_set.all? { |h_a| [h_a, h_b].intersect? } } # only consider the type b houses that intersect with the chosen type a ones
  
        values_to_test = [*1..9] - houses_set.union.select(&:solved?).collect(&:value)
        values_to_test.each do |i|
          fields_set = houses_set.collect { |house| house.select { |f| f.possibilities.include?(i) } }
          intersecting_houses_set = fields_set.collect { |s| s.collect { |f| intersection.select { |house| house.include?(f) }.first } }
          all_intersecting_houses = intersecting_houses_set.union
          next if all_intersecting_houses.include?(nil)
          # for each field in each fields combination in the set:
          # find the house in 'intersection' which it is part of (intersection.select { |house| house.include?(f) }.first)
          
          if all_intersecting_houses.size == houses_set.size && fields_set.all? { |s| s.size >= 2 }
            all_intersecting_houses.each do |house|
              (house - fields_set.union).each { |f| eliminate(f, i) }
            end
          end
        end
      end
    end
  }
}


Jellyfish = rule {
  id :jellyfish
  
  logic {
    house_types = [rows, columns] # jellyfish can never occur with squares -> no generalised version
    
    house_types.var(2).each do |types_pair|
      a, b = types_pair # a is the type of house where we look for aligned candidates,
                        # b is the type of house where we will eliminate the candidates.
                         
      a.comb(4).each do |houses_set|
        intersection = b.select { |h_b| houses_set.all? { |h_a| [h_a, h_b].intersect? } } # only consider the type b houses that intersect with the chosen type a ones
  
        values_to_test = [*1..9] - houses_set.union.select(&:solved?).collect(&:value)
        values_to_test.each do |i|
          fields_set = houses_set.collect { |house| house.select { |f| f.possibilities.include?(i) } }
          intersecting_houses_set = fields_set.collect { |s| s.collect { |f| intersection.select { |house| house.include?(f) }.first } }
          all_intersecting_houses = intersecting_houses_set.union
          next if all_intersecting_houses.include?(nil)
          # for each field in each fields combination in the set:
          # find the house in 'intersection' which it is part of (intersection.select { |house| house.include?(f) }.first)
          
          if all_intersecting_houses.size == houses_set.size && fields_set.all? { |s| s.size >= 2 }
            all_intersecting_houses.each do |house|
              (house - fields_set.union).each { |f| eliminate(f, i) }
            end
          end
        end
      end
    end
  }
}


XWing = rule {
  id :xwing
  name "X-wing"
  
  logic {
    house_types = [rows, columns]
    
    house_types.var(2).each do |types_pair|
      a, b = types_pair # a is the type of house where we look for aligned candidates,
                        # b is the type of house where we will eliminate the candidates.
                         
      a.comb(2).each do |houses_pair| # later veralgemenen naar subset!
        intersection = b.select { |h_b| houses_pair.all? { |h_a| [h_a, h_b].intersect? } } # only consider the type b houses that intersect with the chosen type a ones
  
        values_to_test = [*1..9] - houses_pair.union.select(&:solved?).collect(&:value)
        values_to_test.each do |i|
          fields_set = houses_pair.collect { |house| house.select { |f| f.possibilities.include?(i) } }
          intersecting_houses_set = fields_set.collect { |s| s.collect { |f| intersection.select { |house| house.include?(f) }.first } }
          next if intersecting_houses_set.union.include?(nil)
          # for each field in each fields combination in the set:
          # find the house in 'intersection' which it is part of (intersection.select { |house| house.include?(f) }.first)
          
          if fields_set.all? { |s| s.size == 2 } && intersecting_houses_set.all_equal?
            intersecting_houses_set.first.each do |house|
              (house - fields_set.union).each { |f| eliminate(f, i) }
            end
          end
        end
      end
    end
  }
}
